Allocating more physical space to a certain department of a retail store makes it possible to offer more items and/or brands or make certain items and/or brands more visible. However, space is expensive, and most stores have a fixed amount of space that cannot be extended. Such constraints motivate an optimization of space such that every inch of space available is used in the best (e.g., most profitable) manner.
This space optimization problem can be defined as follows: given a set of departments and a set of fixtures (e.g., shelving units), each department (e.g., category of products) can be realized in a number of sizes (widths and heights) or “realizations,” each size having a different profitability (e.g., measured in sales, turnaround, or net profit). The space optimization problem is to assign departments to fixtures and choose a size for each department, such that the overall length of each fixture is respected, and such that the overall profitability is maximized. Furthermore, a valid solution to the space optimization has to satisfy a number of business rules, such as rules concerning mandatory placements of certain products, optional or mandatory departments, forbidden positions of certain products, required colocations of departments, etc.
The space optimization problem described above is closely related to multiple-choice multiple knapsack problems (MCMKPs). In the MCMKP one has several disjoined classes of items, and a number of knapsacks. Each item has a profit and weight. The task of a solver of the problem is to choose exactly one item from each class and assign it to a knapsack so that the overall profit is maximized while respecting the capacity on the weight for each knapsack. Currently, no solution is available to the above-described space optimization which can handle the extra business constraints, such as mandatory placements or forbidden positions.